package mess;

import java.util.Set;
import java.util.TreeSet;

public class LeeCode_64_overtime {
    public static void main(String[] args) {
        int[][] grid = new int[][]{{1,2},{1,1}};
        System.out.println(minPathSum(grid));
    }
    private static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        TreeSet<Integer> sums = new TreeSet<>();
        backTrick(sums, grid, grid[0][0], 0, 0, m, n);
        System.out.println(sums);
        return sums.first();
    }
    private static void backTrick(Set<Integer> sums, int[][] grid, int sum, int x, int y, int m, int n){
        if (x == m - 1 && y == n - 1){
            sums.add(sum);
            return;
        }
        int temp = sum;
        //右
        if (y < n - 1){
            sum += grid[x][y + 1];
            backTrick(sums, grid, sum, x, y + 1, m, n);
        }
        //下
        if (x < m - 1){
            temp += grid[x + 1][y];
            backTrick(sums, grid, temp, x + 1, y, m, n);
        }
    }
}
